#include <iostream>
#include <vector>
#include <algorithm>

// 策略接口
class SortStrategy {
public:
    virtual ~SortStrategy() {}
    virtual void sort(std::vector<int>& data) const = 0;
};

// 具体策略：快速排序
class QuickSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        std::cout << "Sorting using QuickSort" << std::endl;
        std::sort(data.begin(), data.end());
    }
};

// 具体策略：冒泡排序
class BubbleSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        std::cout << "Sorting using BubbleSort" << std::endl;
        for (size_t i = 0; i < data.size() - 1; ++i) {
            for (size_t j = 0; j < data.size() - i - 1; ++j) {
                if (data[j] > data[j + 1]) {
                    std::swap(data[j], data[j + 1]);
                }
            }
        }
    }
};

// 环境类
class Sorter {
private:
    SortStrategy* strategy;

public:
    Sorter(SortStrategy* strategy = nullptr) : strategy(strategy) {}
    
    ~Sorter() {
        delete strategy;
    }

    void setStrategy(SortStrategy* newStrategy) {
        delete strategy;
        strategy = newStrategy;
    }

    void executeSort(std::vector<int>& data) const {
        if (strategy) {
            strategy->sort(data);
        } else {
            std::cout << "No strategy set!" << std::endl;
        }
    }
};

// 使用示例
int main() {
    std::vector<int> data = {5, 2, 8, 1, 9, 3};
    
    Sorter sorter(new QuickSort());
    sorter.executeSort(data);
    std::cout << "Sorted data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 切换策略
    data = {5, 2, 8, 1, 9, 3}; // 重置数据
    sorter.setStrategy(new BubbleSort());
    sorter.executeSort(data);
    std::cout << "Sorted data: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}